package solutions.leetcode.normal;

import solutions.lib.BaseSolution;

import java.util.LinkedList;
import java.util.List;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/lexicographical-numbers/">386.字典序排数</a>
 */
public class Solution386 extends BaseSolution {

    /*
    给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

    你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

    示例 1：

    输入：n = 13
    输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
    示例 2：

    输入：n = 2
    输出：[1,2]
     */
    public List<Integer> lexicalOrder(int n) {
        List<Integer> rst = new LinkedList<>();
        fill(rst, 0, n);
        return rst;
    }

    private void fill(List<Integer> rst, int now, int max) {
        if (now % 10 == 0) {
            if (now != 0) {
                add(rst, now, max);
            }
            for (int i = 1; i < 10; i++) {
                fill(rst, now + i, max);
            }
        } else {
            if (now <= max) {
                add(rst, now, max);
            }
        }
    }

    private void add(List<Integer> rst, int val, int max) {
        rst.add(val);
        if (val * 10 <= max) {
            fill(rst, val * 10, max);
        }
    }

    /* 非递归解法
    List<Integer> ret = new ArrayList<Integer>();
    int number = 1;
    for (int i = 0; i < n; i++) {
        ret.add(number);
        if (number * 10 <= n) {
            number *= 10;
        } else {
            while (number % 10 == 9 || number + 1 > n) {
                number /= 10;
            }
            number++;
        }
    }
    return ret;
     */

    public static void main(String[] args) {
        Solution386 solution = new Solution386();
        System.out.println(solution.lexicalOrder(2));
    }
}